package leetcode_jz_offer.day1;

/**
 * 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
 * https://leetcode.cn/problems/bao-han-minhan-shu-de-zhan-lcof/
 **/

import java.util.Stack;

/**
 * 思路：借用辅助站，让给任意一个时刻，栈内元素的最小值存储在辅助栈的栈顶元素中
 * 每个元素入栈时都和辅助栈栈顶元素（peek得到）比大小，小的加入辅助栈s2
 * 注意出栈时，辅助栈元素一并弹出
 */
public class MinStack {
    Stack<Integer> s1;
    Stack<Integer> s2;
    public MinStack(){
        s1=new Stack<>();//正常元素入栈情况
        s2=new Stack<>();//辅助栈，最小值保存在该栈
    }
    public void push(int x) {
        s1.push(x);//x加入栈中
        //辅助栈栈顶元素与s1栈中元素比较，较小的加入辅助栈
        if(s2.isEmpty()){
            s2.push(x);
        }else{
            s2.push(Math.min(x,s2.peek()));
        }//此时辅助栈栈顶元素就是当前s1栈中所有元素中的最小元素
    }

    public void pop() {//弹出时主站和辅助栈同时弹出
        s1.pop();
        s2.pop();
    }

    public int top() {//返回栈顶元素
        return s1.peek();
    }

    public int min() {//返回所有元素中的最小元素
        return s2.peek();
    }

}
